package math;
import java.util.*;
import java.util.stream.Collector;
import java.util.stream.Collectors;

import org.junit.Test;

import utils.ArrayGenerator;
import utils.BracketUtils;
public class Ex54 {
    class Solution {

        //此题的flags数组可以变成对matrix的修改
        public List<Integer> spiralOrder1(int[][] matrix) {
            List<Integer> res = new ArrayList<>();
            int d = 0, m = matrix.length, n = matrix[0].length, t = Math.min(m, n);
            boolean[][] flags = new boolean[m][n];
            while (d < (t + 1) / 2) {
                int l = d;
                int r = n - d - 1;
                int b = m - d - 1;
                int u = d;
                for (int i = l; i <= r; i++) {
                    if (!flags[u][i]) {
                        res.add(matrix[u][i]);
                        flags[u][i] = true;
                    }
                }
                for (int j = u + 1; j <= b; j++) {
                    if (!flags[j][r]) {
                        res.add(matrix[j][r]);
                        flags[j][r] = true;
                    }
                }
                for (int i = r - 1; i > l; i--) {
                    if (!flags[b][i]) {
                        res.add(matrix[b][i]);
                        flags[b][i] = true;
                    }
                }
                for (int j = b; j > u; j--) {
                    if (!flags[j][l]) {
                        res.add(matrix[j][l]);
                        flags[j][l] = true;
                    }
                }
                d++;
            }
            return res;
        }

        //将遍历过的一列或者一列往中间缩进,就不需要额外的数组了【或者可以将额外数组换值】
        public List<Integer> spiralOrder(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            int u = 0, l = 0, r = n - 1, b = m - 1;
            List<Integer> res = new ArrayList<>();
            while (true) {
                for (int i = l; i <= r; i++) res.add(matrix[u][i]);
                if (++u > b) break;
                for (int i = u; i <= b; i++) res.add(matrix[i][r]);
                if (--r < l) break;
                for (int i = r; i >= l; i--) res.add(matrix[b][i]);
                if (--b < u) break;
                for (int i = b; i >= u; i--) res.add(matrix[i][l]);
                if (++l > r) break;
            }
            return res;
        }
    }

    @Test
    public void test() {
        // int[][] nums = BracketUtils.to2DArray("[[1,2,3],[4,5,6],[7,8,9]]");
        int[][] nums = BracketUtils.to2DArray("[[1,2,3,4],[5,6,7,8],[9,10,11,12]]");
        // int[][] nums = BracketUtils.to2DArray("[[3],[2]]");

        Solution s = new Solution();

        System.out.println(s.spiralOrder(nums));
        
      /*   int[][] num = new int[10][];
        for (int i = 0; i < 10; i++) {
            num[i] = ArrayGenerator.getArray(100, 10);
        }
        System.out.println(num.length);
        List<List<Integer>> n = new ArrayList<>();
        for (int i = 0; i < num.length; i++) {
            n.add(Arrays.stream(num[i]).boxed().collect(Collectors.toList()));
        }
        // List<Integer> res = s.spiralOrder(num);
        System.out.println(n); */
    }

   
}
